package com.jojo.elementary.day8_linkedList;

import com.jojo.elementary.entity.ListNode;

/**
 * 206、反转链表
 *
 * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表
 *
 * 示例 1：
 * 输入：head = [1,2,3,4,5]
 * 输出：[5,4,3,2,1]
 *
 * 示例 2：
 * 输入：head = [1,2]
 * 输出：[2,1]
 *
 * 示例 3：
 * 输入：head = []
 * 输出：[]
 *
 * 进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
 */
public class ReversalList {

    /** myCode 迭代 */
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        ListNode pre = null;
        ListNode cur = head;
        ListNode next;
        while(cur != null){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    /** pe. 递归 */
    public ListNode reverseList2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList2(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    public static void main(String[] args) {
        int[] arr = {1,2,6,3,4,5,6};
        ListNode head = new ListNode(arr[0]);
        ListNode cur = head;
        for (int i = 1;i < arr.length;i++){
            cur.next = new ListNode(arr[i]);
            cur = cur.next;
        }
        ReversalList reversalList = new ReversalList();
        ListNode listNode = reversalList.reverseList(head);
        while (listNode != null){
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }
}
